package com.sicheng.datastruct.tree;

import lombok.AllArgsConstructor;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/8 16:11
 */
@AllArgsConstructor
@SuppressWarnings("unused")
public class ArrTree {
    /**
     * 顺序存储二叉树
     * 1)顺序二叉树通常只考虑完全二叉树
     * 2)第n个元素的左子节点为  2*n + 1
     * 3)第n个元素的右子节点为  2*n + 2
     * 4)第n个元素的父节点为   (n-1) / 2
     */
    private final int[] node;

    //前序遍历
    public void preOrder() {
        if (node != null && node.length > 0) {
            this.preOrder(0);
        } else
            System.out.println("树为空！！！！");
    }
    private void preOrder(int index) {
        System.out.print(node[index] + " ");
        if (2 * index + 1 < node.length) {
            preOrder(2 * index + 1);
        }
        if (2 * index + 2 < node.length)
            preOrder(2 * index + 2);
    }

    //中序遍历
    public void infixOrder() {
        if (node != null && node.length > 0) {
            this.infixOrder(0);
        } else
            System.out.println("树为空！！！！");
    }
    private void infixOrder(int index) {
        if (index * 2 + 1 < node.length)
            infixOrder(index * 2 + 1);
        System.out.print(node[index] + " ");
        if (index * 2 + 2 < node.length)
            infixOrder(index * 2 + 2);
    }

    //后序遍历
    public void postOder() {
        if (node != null && node.length > 0) {
            this.postOder(0);
        } else
            System.out.println("树为空！！！！");
    }
    private void postOder(int index) {
        if (index * 2 + 1 < node.length)
            postOder(index * 2 + 1);
        if (index * 2 + 2 < node.length)
            postOder(index * 2 + 2);

        System.out.print(node[index] + " ");
    }

    public static void main(String[] args) {
        int[] node = {1, 2, 3, 4, 5, 6, 7};
        ArrTree arrTree = new ArrTree(node);
        arrTree.preOrder();//1,2,4,5,3,6,7
        System.out.println();
        arrTree.infixOrder();//4,2,5,1,6,3,7
        System.out.println();
        arrTree.postOder();//4,5,2,6,7,3,1
    }
}
